package com.peng.leetcode.backtracking;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * MaxUncrossedLines
 *
 * 1035. 不相交的线
 *
 *@author lupeng
 *Created on 2021-05-21
 */
public class MaxUncrossedLines {

    public static void main(String[] args) {
        int[] nums1 = {2, 5, 1, 2, 5};
        int[] nums2 = {10, 5, 2, 1, 5, 2};
    }

    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

    private Map<Integer, Integer> indexMap = new HashMap<>();

    private int answer = 0;

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        for (int i = 0; i < nums2.length; i++) {
            int num = nums2[i];
            indexMap.put(num, i);
        }
        backTracking(nums1, 0, 0);
        return answer;
    }

    private void backTracking(int[] nums1, int index, int size) {
        if (index >= nums1.length) {
            return;
        }
        answer = Math.max(answer, size);
        int num = nums1[index];

        //获取
        Integer nums2Index = indexMap.get(num);
        if (nums2Index < maxHeap.peek()) {
            maxHeap.poll();
            maxHeap.offer(nums2Index);
            backTracking(nums1, index + 1, size);
        } else {
            maxHeap.offer(nums2Index);
            backTracking(nums1, index + 1, size + 1);
        }

        //不获取
        backTracking(nums1, index + 1, size);
    }
}
